This invention deals with a method for statistically improving routing within an internet, and more particularly for improving next hop selection between internetwork routers.
Modem digital networks operate using different transmission media and interconnect on demand a very large number of users (e.g. hosts) and applications through fairly complex digital communication networks.
Due to the large variety of users""profiles and distributed applications, network traffic is making greater bandwidth demands, exhibits less regular patterns and must be delivered to more uses and more widely separated destinations. This has driven the development fast packet switching techniques in which data from different origins are segmented into fixed or variable length packets (generically referred to as datagrams, with both expressions xe2x80x9cpacketsxe2x80x9d and xe2x80x9cdatagramsxe2x80x9d being equally used herein) and then transferred, over high speed digital networks, between data source and target terminal equipments.
Several types of networks have been installed throughout the world, which need to be interconnected (e.g. via so called Routers) to optimize the possibilities of organizing traffic between source host terminal(s) and.target host terminal(s) located anywhere in the world. This is made possible by using so-called internetworking.
Internetwork (also referred to as internet) facilities use a set of networking protocols such as Transmission ControlProtocol/Internet Protocol (TCP/IP) developed to allow cooperating host computers to share resources across the internetwork. TCP/IP is a set of data communication protocols that are referred to as an internet protocol (IP) suite. Because TCP and IP are the best known, it has become common to use the term TCP/IP to refer to the whole protocol family. TCP and IP are two of the protocols in this suite. Other protocols of the suite include User Datagram Protocol (UDP), Address Resolution Protocol (ARP), and Real Time Protocol (RTP).
An internet may be viewed as a collection of heterogeneous and independent networks using TCP/IP and connected together by routers. The administrative responsibilities for an internet (e.g., assignment of IP addresses and domain names) can be within a single network (LAN) or distributed among multiple networks. To enable sending data from any source host to any target host connected to the internet, routing protocols have been defined. They include Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) protocol using personalized so-called Routing Tables to define inter-router paths on a hop-by-hop basis, asynchronously from source to target. To that end, internetwork routers keep exchanging up-to-date network topology information and building up their Routing Tables.
Accordingly, whenever a source host (S) needs to send a data packet through the internet to a target host (T), S contacts its xe2x80x9cdefaultxe2x80x9d router asking the router to send the packet toward the target (T). Routing within any given router R is based only on target identification. When running OSPF, the system looks for the xe2x80x9cbestxe2x80x9d path toward the destination T. By xe2x80x9cbestxe2x80x9d path one usually means shortest (i.e. involving minimum router xe2x80x9chopsxe2x80x9d). But for purposes of the invention, a xe2x80x9cbestxe2x80x9d path may also take into account minimum cost and optimized bandwidth occupation. Lleased links costs may need to be taken into consideration when setting the path throughout the internet networks. In case of equivalent paths OSPF usually selects the first path identified within router Table.
Some improvements have been made in OSPF to avoid always using same paths which can lead to overloading some network paths and concurrent underutilization of others. For instance, in case of xe2x80x9cequivalentxe2x80x9d paths being identified some kind of xe2x80x9cround robinxe2x80x9d or per packet multipath algorithm may be executed to achieve load balancing. To further illustrate the above, consider an example of operation (see FIG. 1). Assume source IP Host (1) transmits IP traffic to IP destination Host(9). All this traffic goes to IP Router 1 (R1).Router 1 learns the routes to IP Destination Host (9) using the OSPF routing protocol. As schematically illustrated in FIG. 1, there are three different routes from IP Router 1 to IP destination host (9), one via Router R2 (path 3), one via Router R3 (path 4) and one via Router R4 (path 5). Each route has an associated xe2x80x9ccostxe2x80x9d. OSPF selects the route with lowest cost and all traffic is sent over that selected route. Where xe2x80x9cequivalentxe2x80x9d routes are detected, the first route in the Router R1 Table is selected.
However, when the OSPF Per Packet Multipath option is enabled in IP Router R1 and when the costs of all three routes are equal, IP Router R1 keeps the three routes. IP traffic is then transferred equally on all these routes, in round robin operating mode, on a per packet basis. A first IP packet to be transmitted is sent on the first route (Route (3)), a second IP packet is sent over the second route (Route (4)), a third packet is sent on third route (Route (5)), a fourth packet is then assigned the first route (Route (3)) again, and so on.
In practice, the system operation is a little more complex. Each network router includes a routing table and a cache storing the actual path(s) to be followed. Then the system may assign a different route to each packet or keep sending packets over the same route until the cache is refreshed, in which case the router switches to next route.
This enables balancing the IP traffic on all available xe2x80x9cequivalentxe2x80x9d routes, and accordingly, balances the traffic, as much as possible, over equivalent routes across the internet.
However, this function uses a static cost parameter, set at network configuration time. It does not take any congestion on one of the xe2x80x9cequivalentxe2x80x9d routes into consideration, while congestion may and actually does, occur.
Assume one of the routes shown in FIG. 1, e.g. route (5), is congested due to the maximum bandwidth being used on the connection between IP Router R1 and Router R4. In this case, the OSPF Per Packet Multipath Function keeps using the route (5) because the OSPF cost does not change even though the link (5) is congested. IP Router R1 may still distribute packets over all three routes, but the packets assigned to route (5) will be queued in Router R1 until link 5 exits from congestion. The IP Destination Host (9) then receives and acknowledges all the IP packets, except those transmitted over path 5. The Destination Host must then wait for the IP packets on path (5) before it can provide the complete set of data to its application. As a consequence, with the OSPF Per Packet Multipath operating mode, the delay introduced in the connection between Source and Destination (Target) hosts is the highest delay on all the different assigned routes. In addition, if three TCP Connections are established from IP source (1) to destination (9) for each of the three connections, IP packets are sent over the three different routes. This means that all the three connections will be impacted by the delay introduced on route (5).
More precisely, when packets P1, P2, P3 . . . are sent by any source host toward a Target host, the target host acknowledges reception of the last received packet.
In fact acknowledgment addresses a number of bytes, but as far as the invention is concerned that does not affect the rationale. Assuming then P2 misses, the target host shall keep acknowledging P1, even if P3, . . . are received. The system runs then a Fast Recovery protocol to generate retransmission of P2 from the source host until P2 is received.
In any case the overall consequence is that the efficiency of the network is seriously affected. Assuming one path goes through a 200 Kbps link and one or several go through 1 Mbps link(s), the practical result is that the system might be biased by the 200 Kbps rate of operation.
One object of this invention is to provide a method and system to enable balancing IP traffic on all available equivalent routes without being seriously impacted by congestion phenomenon occurring on one of said routes.
Another object of this invention is to provide a method and system to allow using the OSPF Per Packet Multipath Function without impacting all the connections when a route becomes congested.
A further object of this invention is to provide a method and system enabling using the OSPF Per Packet Multipath Function without creating network performance degradation in case of congestion on any selected route while taking into consideration cost or bandwidth criteria.
These and other objects, features and advantages of this invention will be made apparent from the following more detailed description of a best mode of implementation.
This invention deals with a method for improving next hop selection between internet routers (R) defined by their respective IP addresses, to orient the traffic between a source host (S) identified by a source IP address and a source port identification and a destination host(T) defined by a target port identification. To that end, equivalent routes toward the destination (T) host are identified, each of said equivalent routes being defined by next router (R) IP address. A first predefined logical combination between said source (S) IP address, S port identification and T port identification is performed to derive a so-called connection identifier (HO). Then a second predefined logical operation between HO and each next equivalent route R IP address is performed, to derive so-called next hop selection identifiers therefrom. And finally next hop route is selected based on a predefined criterion among said selection identifiers.